Ready to start BFS. Click "Next Step".
Queue (FIFO):
Visit Order:

Breadth-First Search (BFS)

BFS (Обход в ширину) — это стратегия посещения узлов дерева уровень за уровнем. Сначала посещается корень, затем все его непосредственные дети, затем внуки и так далее.

Key Characteristics:

  • Использует Queue (Очередь) для хранения узлов (First-In, First-Out).
  • Сложность: $O(V + E)$, где $V$ — узлы, $E$ — ребра.
  • Применяется для поиска кратчайшего пути в невзвешенных структурах.

Iterative BFS (std::queue)

#include <queue>

void bfs(Node* root) {
    if (!root) return;
    
    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();

        std::cout << curr->val << " ";

        // Добавляем детей в очередь слева направо
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}